package lc;
import org.junit.*;
public class Ex410 {
    class Solution {
        public int splitArray(int[] nums, int m) {
            /** 2.二分
            二分的场景：在有范围的整数中查找一个数；
            二分查找的依据：问题具有单调性
            即：若要查找元素x，定义的查找依据是f(x),那么一定满足f(a)>f(x), a>x...
    
            1、查找分割数组最大值的最小值，设为x；
            2. 函数：f(x)为x可以确定的分割数量
    
            任意位置a，若f(a)<f(x),证明分割数量太少，比最佳方案还少，必然导致a>x；
            若f(a)=f(x),也无法确定a==x;(分割数正确，分割方式不唯一)
    
            若f(a)=f(x)+1,且f(a-1)=f(x) （a-1是临界点）
            则：x=a-1
    
            f(x)单调递减：
            f(x) < m, x > b;
                 == m, x∈[a, b]
                 > m, x < a
            所求：b
             */
            int max = 0, sum = 0;
             for (int num: nums) {
                 max = Math.max(max, num);
                 sum += num;
             }
             //left分割为len段（f(left)=len），right化为1段(f(right)=1)
             int left = max, right = sum;
            while (left < right) {
                //当前设定的a(片段最大值)
                int mid = (right - left) / 2 + left;
                int splits = split(nums, mid);//等价于f(x)
                if (splits > m) {
                    //片段不足，分割度不够，证明最大值太小，缩小a
                    left = mid + 1;
                } else {
                    right = mid;
                }
            }
            return left;
        }
        //设定一个片段最大值为max，看能划分为几个片段
        public int split(int[] nums, int max) {
            int splits = 1, cur = 0;
            for (int n: nums) {
                if (cur + n > max) {
                    //不能加上这个数，此片段到此结束
                    splits++;
                    cur = 0;
                }
                cur += n;
            }
            return splits;
        }
    }

    @Test
    public void test() {
        Solution s = new Solution();
        int[] nums = new int[]{7,2,5,10,8};
        System.out.println(s.splitArray(nums, 2));
    }

    @Test
    public void test2() {
        Solution2 s = new Solution2();
        int[] nums = new int[]{7,2,5,10,8};
        System.out.println(s.splitArray(nums, 2));
    }

    class Solution2 {

        public int splitArray(int[] nums, int m) {
            int lo = 0, hi = 0; //段数最小为1，全部；最大为n，即为最大者
            for (int n: nums) {
                lo = Math.max(lo, n);
                hi += n;
            }
            while (lo < hi) {
                int mid = (hi - lo) / 2 + lo;
                int cnt = count(nums, mid);
                if (cnt > m) {
                    //划分不动
                    lo = mid + 1;
                } else {
                    hi = mid; //更加优化
                }
            }
            return lo;
        }

        //f(m)=x; m是最大值，x是分的段数
        public int count(int[] nums, int m) {
            int x = 1, sum = 0;
            for (int n: nums) {
                if (n + sum > m) {
                    x++;
                    sum = 0;
                }
                sum += n;
            }
            return x;
        }
    }
}
